package org.patterns.structural.adapter;

//快速排序类：适配者
public class QuickSort {
    public int[] quickSort(int array[]) {
        sort(array, 0, array.length - 1);
        return array;
    }

    /**
     * 使用快速排序算法对数组进行排序
     * 该方法递归地将数组分为两部分，并对每部分进行排序
     *
     * @param nums  待排序的数组
     * @param left  数组的起始索引
     * @param right 数组的结束索引
     */
    public void sort(int[] nums, int left, int right) {
        // 检查数组的起始索引是否小于结束索引，确保数组至少有两个元素
        if (left < right) {
            // 哨兵划分，将数组分为两部分并返回分割点的索引
            int pivot = partition(nums, left, right);
            // 对分割点左侧的数组进行递归排序
            sort(nums, left, pivot - 1);
            // 对分割点右侧的数组进行递归排序
            sort(nums, pivot + 1, right);
        }
    }

    /**
     * 哨兵划分，使得左边部分的所有元素都不大于右边部分的所有元素
     * 此方法主要用于快速排序中，以确定分区的位置
     *
     * @param nums  数组，其元素将被重新排列
     * @param left  分区起始索引
     * @param right 分区结束索引
     * @return 分区点的索引，即所有小于等于基准值的元素中的最后一个元素的索引
     */
    public int partition(int[] nums, int left, int right) {
        // 以 nums[left] 为基准数
        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= nums[left])
                j--;          // 从右向左找首个小于基准数的元素
            while (i < j && nums[i] <= nums[left])
                i++;          // 从左向右找首个大于基准数的元素
            swap(nums, i, j); // 交换这两个元素
        }
        swap(nums, i, left);  // 将基准数交换至两子数组的分界线
        return i;             // 返回基准数的索引
    }

    /**
     * 交换数组中两个指定位置的元素
     *
     * @param a 数组
     * @param i 位置1
     * @param j 位置2
     */
    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}